package main

import (
	"fmt"
	"time"
)

func dfs_provices(isConnected [][]int, r int, c int) {
	// fmt.Println("====in=====")
	// fmt.Println(r, c)
	// fmt.Println(isConnected)
	// fmt.Println("=========")
	// fmt.Println()

	if !(0 <= r && r < len(isConnected) && 0 <= c && c < len(isConnected[0])) {
		return
	}

	if isConnected[r][c] != 1 {
		return
	}

	isConnected[r][c] = 2
	// fmt.Println(isConnected)
	// fmt.Println("=====out====")
	// fmt.Println()
	for i := 0; i < len(isConnected); i++ {
		dfs_provices(isConnected, i, c)
		dfs_provices(isConnected, r, i)
	}

}

func findCircleNum(isConnected [][]int) int {
	num_provinces := 0
	m := len(isConnected)
	n := len(isConnected[0])

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if isConnected[i][j] == 1 {
				num_provinces++
				dfs_provices(isConnected, i, j)
			}
		}
	}
	return num_provinces
}

func main() {
	start := time.Now()
	isConnected := [][]int{{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 1}}
	result := findCircleNum(isConnected)
	cost := time.Since(start)
	fmt.Println("result:", result)
	fmt.Println(cost)
}
